﻿#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<iostream>
using namespace std;


//二维多状态dp

//123. 买卖股票的最佳时机 III
class Solution {
public:
    static int ITN;
    int maxProfit(vector<int> prices)
    {
        // 第i天结束时的的最大利润
        // 1.买入状态(交易次数0、1、2)
        // 2.卖出状态(交易次数0、1、2)

        int n = prices.size();
        vector<vector<int>> dpb(n, vector<int>(3, ITN));//买入状态
        vector<vector<int>> dps(n, vector<int>(3, ITN));//卖出状态

        // 初始化
        dpb[0][0] = -prices[0];
        dps[0][0] = 0;

        // dpb[i][j]表⽰: 第i天结束后, 完成了j次交易，处于[买⼊]状态，此时的最⼤利润
        // dps[i][j]表⽰: 第i天结束后, 完成了j次交易，处于[卖出]状态，此时的最⼤利润

        // 填表
        for (int i = 1; i < n; i++)
        {
            // 成功卖出一次才算得上一次交易
            for (int j = 0; j < 3; j++)
            {
                dpb[i][j] = max(dpb[i - 1][j], dps[i - 1][j] - prices[i]);
                dps[i][j] = dps[i - 1][j];
                if (j > 0)
                {
                    dps[i][j] = max(dps[i][j], dpb[i - 1][j - 1] + prices[i]);
                }
            }
        }
        return max(max(dps[n - 1][0], dps[n - 1][1]), dps[n - 1][2]);

    }
};
//类内静态成员 类内声明类外定义
int Solution::ITN = -0x3f3f3f3f;

int main()
{
    Solution s;
    s.maxProfit({ 3,3,5,0,0,3,1,4 });

    return 0;
}


//188. 买卖股票的最佳时机 IV
class Solution
{
public:
    const int ITN = -0x3f3f3f3f;

    int maxProfit(int k, vector<int>& prices)
    {
        // 第i天结束时的的最大利润
        // 1.买入状态(交易次数0、1、2...k)
        // 2.卖出状态(交易次数0、1、2...k)

        int n = prices.size();
        vector<vector<int>> dpb(n, vector<int>(k + 1, ITN));
        vector<vector<int>> dps(n, vector<int>(k + 1, ITN));

        // 初始化
        dpb[0][0] = -prices[0];
        dps[0][0] = 0;

        // dpb[i][j]表⽰: 第i天结束后, 完成了j次交易，处于[买⼊]状态，此时的最⼤利润
        // dps[i][j]表⽰: 第i天结束后, 完成了j次交易，处于[卖出]状态，此时的最⼤利润
        for (int i = 1; i < n; i++)
        {
            // 成功卖出一次才算得上一次交易7
            for (int j = 0; j <= k; j++)
            {
                dpb[i][j] = max(dpb[i - 1][j], dps[i - 1][j] - prices[i]);
                dps[i][j] = dps[i - 1][j];
                if (j > 0)
                {
                    dps[i][j] = max(dps[i][j], dpb[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int ret = 0;
        for (int i = 0; i <= k; i++)
        {
            ret = max(ret, dps[n - 1][i]);
        }
        return ret;
    }
};